{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Cost to Connect Two Groups of Points"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #bitmask #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #状态压缩 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: connectTwoGroups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #连通两组点的最小成本"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两组点，其中第一组中有 <code>size<sub>1</sub></code> 个点，第二组中有 <code>size<sub>2</sub></code> 个点，且 <code>size<sub>1</sub> &gt;= size<sub>2</sub></code> 。</p>\n",
    "\n",
    "<p>任意两点间的连接成本 <code>cost</code> 由大小为 <code>size<sub>1</sub> x size<sub>2</sub></code> 矩阵给出，其中 <code>cost[i][j]</code> 是第一组中的点 <code>i</code> 和第二组中的点 <code>j</code> 的连接成本。<strong>如果两个组中的每个点都与另一组中的一个或多个点连接，则称这两组点是连通的。</strong>换言之，第一组中的每个点必须至少与第二组中的一个点连接，且第二组中的每个点必须至少与第一组中的一个点连接。</p>\n",
    "\n",
    "<p>返回连通两组点所需的最小成本。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/09/20/ex1.jpg\" style=\"height: 243px; width: 322px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>cost = [[15, 96], [36, 2]]\n",
    "<strong>输出：</strong>17\n",
    "<strong>解释：</strong>连通两组点的最佳方法是：\n",
    "1--A\n",
    "2--B\n",
    "总成本为 17 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/09/20/ex2.jpg\" style=\"height: 403px; width: 322px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>连通两组点的最佳方法是：\n",
    "1--A\n",
    "2--B\n",
    "2--C\n",
    "3--A\n",
    "最小成本为 4 。\n",
    "请注意，虽然有多个点连接到第一组中的点 2 和第二组中的点 A ，但由于题目并不限制连接点的数目，所以只需要关心最低总成本。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]\n",
    "<strong>输出：</strong>10\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>size<sub>1</sub> == cost.length</code></li>\n",
    "\t<li><code>size<sub>2</sub> == cost[i].length</code></li>\n",
    "\t<li><code>1 &lt;= size<sub>1</sub>, size<sub>2</sub> &lt;= 12</code></li>\n",
    "\t<li><code>size<sub>1</sub> &gt;=&nbsp;size<sub>2</sub></code></li>\n",
    "\t<li><code>0 &lt;= cost[i][j] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-cost-to-connect-two-groups-of-points](https://leetcode.cn/problems/minimum-cost-to-connect-two-groups-of-points/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-cost-to-connect-two-groups-of-points](https://leetcode.cn/problems/minimum-cost-to-connect-two-groups-of-points/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[15,96],[36,2]]', '[[1,3,5],[4,1,1],[1,5,3]]', '[[2,5,1],[3,4,7],[8,1,2],[6,2,4],[3,8,8]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        ##矩阵每行每列都至少选一个坐标\n",
    "        n,m=len(cost),len(cost[0])\n",
    "        f=[0]*(1<<m)\n",
    "        for i,col in enumerate(zip(*cost)):\n",
    "            f[1<<i]=min(col)\n",
    "        for j in range(1<<m):\n",
    "            f[j]=f[j&(j-1)]+f[j&(-j)]\n",
    "        for row in cost:\n",
    "            for j in range((1<<m)-1,-1,-1):\n",
    "                f[j] = min(f[j & ~(1 << k)] + c for k, c in enumerate(row))\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # dp = [inf for _ in range(1 << n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(1 << n)]\n",
    "        #     for i, c in enumerate(row) :\n",
    "        #         for j, d in enumerate(dp) :\n",
    "        #             k = j | (1 << i)\n",
    "        #             x[k] = min(x[k], d + c, dp[k] + c, x[j] + c)\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # n = 1 << n\n",
    "\n",
    "        # dp = [inf for _ in range(n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(n)]\n",
    "        #     for s in range(n) :\n",
    "        #         for k, c in enumerate(row) :\n",
    "        #             if s & (1 << k) :\n",
    "        #                 s_k = s ^ (1 << k)\n",
    "        #                 # x[s] = min(x[s], x[s_k] + c, dp[s] + c, dp[s_k] + c)\n",
    "        #                 if x[s] > (tmp := x[s_k] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #                 if x[s] > (tmp := dp[s] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #                 if x[s] > (tmp := dp[s_k] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # min_cost = list(map(min, zip(*cost)))\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j) :\n",
    "        #     if i < 0 :\n",
    "        #         return sum(c for k, c in enumerate(min_cost) if j & (1 << k))\n",
    "        #     return min(dfs(i - 1, j & ~(1 << k)) + c for k, c in enumerate(cost[i]))\n",
    "        # return dfs(m - 1, (1 << n) - 1)\n",
    "\n",
    "\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # min_cost = list(map(min, zip(*cost)))\n",
    "        # dp = [[0 for _ in range(1 << n)] for _ in range(m + 1)]\n",
    "\n",
    "        # for j in range(1 << n) :\n",
    "        #     dp[0][j] = sum(c for k, c in enumerate(min_cost) if j & (1 << k))\n",
    "\n",
    "        # for i, row in enumerate(cost) :\n",
    "        #     for j in range(1 << n) :\n",
    "        #         dp[i + 1][j] = min(dp[i][j & ~(1 << k)] + c for k, c in enumerate(row))\n",
    "        # return dp[-1][-1]\n",
    "        \n",
    "        m = len(cost)\n",
    "        n = len(cost[0])\n",
    "        dp = [0 for _ in range(1 << n)]\n",
    "        for j, c in enumerate(map(min, zip(*cost))) :\n",
    "            bit = 1 << j\n",
    "            for k in range(bit) :\n",
    "                dp[k | bit] = dp[k] + c\n",
    "        for row in cost :\n",
    "            for j in range((1 << n) - 1, - 1, - 1) :\n",
    "                dp[j] = min(dp[j & ~(1 << k)] + c for k, c in enumerate(row))\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # dp = [inf for _ in range(1 << n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(1 << n)]\n",
    "        #     for i, c in enumerate(row) :\n",
    "        #         for j, d in enumerate(dp) :\n",
    "        #             k = j | (1 << i)\n",
    "        #             x[k] = min(x[k], d + c, dp[k] + c, x[j] + c)\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # n = 1 << n\n",
    "\n",
    "        # dp = [inf for _ in range(n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(n)]\n",
    "        #     for s in range(n) :\n",
    "        #         for k, c in enumerate(row) :\n",
    "        #             if s & (1 << k) :\n",
    "        #                 s_k = s ^ (1 << k)\n",
    "        #                 # x[s] = min(x[s], x[s_k] + c, dp[s] + c, dp[s_k] + c)\n",
    "        #                 if x[s] > (tmp := x[s_k] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #                 if x[s] > (tmp := dp[s] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #                 if x[s] > (tmp := dp[s_k] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # min_cost = list(map(min, zip(*cost)))\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j) :\n",
    "        #     if i < 0 :\n",
    "        #         return sum(c for k, c in enumerate(min_cost) if j & (1 << k))\n",
    "        #     return min(dfs(i - 1, j & ~(1 << k)) + c for k, c in enumerate(cost[i]))\n",
    "        # return dfs(m - 1, (1 << n) - 1)\n",
    "\n",
    "\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # min_cost = list(map(min, zip(*cost)))\n",
    "        # dp = [[0 for _ in range(1 << n)] for _ in range(m + 1)]\n",
    "\n",
    "        # for j in range(1 << n) :\n",
    "        #     dp[0][j] = sum(c for k, c in enumerate(min_cost) if j & (1 << k))\n",
    "\n",
    "        # for i, row in enumerate(cost) :\n",
    "        #     for j in range(1 << n) :\n",
    "        #         dp[i + 1][j] = min(dp[i][j & ~(1 << k)] + c for k, c in enumerate(row))\n",
    "        # return dp[-1][-1]\n",
    "        \n",
    "        m = len(cost)\n",
    "        n = len(cost[0])\n",
    "        dp = [0 for _ in range(1 << n)]\n",
    "        for j, c in enumerate(map(min, zip(*cost))) :\n",
    "            bit = 1 << j\n",
    "            for k in range(bit) :\n",
    "                dp[k | bit] = dp[k] + c\n",
    "        for row in cost :\n",
    "            for j in range((1 << n) - 1, - 1, - 1) :\n",
    "                dp[j] = min(dp[j & ~(1 << k)] + c for k, c in enumerate(row))\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # dp = [inf for _ in range(1 << n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(1 << n)]\n",
    "        #     for i, c in enumerate(row) :\n",
    "        #         for j, d in enumerate(dp) :\n",
    "        #             k = j | (1 << i)\n",
    "        #             x[k] = min(x[k], d + c, dp[k] + c, x[j] + c)\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # n = 1 << n\n",
    "\n",
    "        # dp = [inf for _ in range(n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(n)]\n",
    "        #     for s in range(n) :\n",
    "        #         for k, c in enumerate(row) :\n",
    "        #             if s & (1 << k) :\n",
    "        #                 s_k = s ^ (1 << k)\n",
    "        #                 # x[s] = min(x[s], x[s_k] + c, dp[s] + c, dp[s_k] + c)\n",
    "        #                 if x[s] > (tmp := x[s_k] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #                 if x[s] > (tmp := dp[s] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #                 if x[s] > (tmp := dp[s_k] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # min_cost = list(map(min, zip(*cost)))\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j) :\n",
    "        #     if i < 0 :\n",
    "        #         return sum(c for k, c in enumerate(min_cost) if j & (1 << k))\n",
    "        #     return min(dfs(i - 1, j & ~(1 << k)) + c for k, c in enumerate(cost[i]))\n",
    "        # return dfs(m - 1, (1 << n) - 1)\n",
    "\n",
    "\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # min_cost = list(map(min, zip(*cost)))\n",
    "        # dp = [[0 for _ in range(1 << n)] for _ in range(m + 1)]\n",
    "\n",
    "        # for j in range(1 << n) :\n",
    "        #     dp[0][j] = sum(c for k, c in enumerate(min_cost) if j & (1 << k))\n",
    "\n",
    "        # for i, row in enumerate(cost) :\n",
    "        #     for j in range(1 << n) :\n",
    "        #         dp[i + 1][j] = min(dp[i][j & ~(1 << k)] + c for k, c in enumerate(row))\n",
    "        # return dp[-1][-1]\n",
    "        \n",
    "        m = len(cost)\n",
    "        n = len(cost[0])\n",
    "        dp = [0 for _ in range(1 << n)]\n",
    "        for j, c in enumerate(map(min, zip(*cost))) :\n",
    "            bit = 1 << j\n",
    "            for k in range(bit) :\n",
    "                dp[k | bit] = dp[k] + c\n",
    "        for row in cost :\n",
    "            for j in range((1 << n) - 1, - 1, - 1) :\n",
    "                dp[j] = min(dp[j & ~(1 << k)] + c for k, c in enumerate(row))\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # 1. 递归\n",
    "        # n, m = len(cost), len(cost[0])\n",
    "        # min_cost = [min(col) for col in zip(*cost)] # 每一列的最小值\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i:int, j:int) -> int:\n",
    "        #     if i < 0:\n",
    "        #         return sum(c for k, c in enumerate(min_cost) if j >> k & 1)\n",
    "        #     return min(dfs(i - 1, j &~ (1 << k)) + c for k, c in enumerate(cost[i])) # 第一组的点i与第二组的点k\n",
    "        # return dfs(n - 1, (1 << n) - 1)\n",
    "\n",
    "        # 2. 递推\n",
    "        f = [0] * (1 << len(cost[0]))\n",
    "        for j, mn in enumerate(map(min, zip(*cost))):\n",
    "            bit = 1 << j\n",
    "            for mask in range(bit):\n",
    "                f[bit | mask] = f[mask] + mn\n",
    "        for row in cost:\n",
    "            for j in range(len(f) - 1, -1, -1):\n",
    "                f[j] = min(f[j &~ (1 << k)] + c for k, c in enumerate(row))\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # dp = [inf for _ in range(1 << n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(1 << n)]\n",
    "        #     for i, c in enumerate(row) :\n",
    "        #         for j, d in enumerate(dp) :\n",
    "        #             k = j | (1 << i)\n",
    "        #             x[k] = min(x[k], d + c, dp[k] + c, x[j] + c)\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "        m = len(cost)\n",
    "        n = len(cost[0])\n",
    "        n = 1 << n\n",
    "\n",
    "        dp = [inf for _ in range(n)]\n",
    "        dp[0] = 0\n",
    "        for row in cost :\n",
    "            x = [inf for _ in range(n)]\n",
    "            for s in range(n) :\n",
    "                for k, c in enumerate(row) :\n",
    "                    if s & (1 << k) :\n",
    "                        s_k = s ^ (1 << k)\n",
    "                        x[s] = min(x[s], x[s_k] + c, dp[s] + c, dp[s_k] + c)\n",
    "                        # if x[s] > (tmp := x[s_k] + c) :\n",
    "                        #     x[s] = tmp\n",
    "                        # if x[s] > (tmp := dp[s] + c) :\n",
    "                        #     x[s] = tmp\n",
    "                        # if x[s] > (tmp := dp[s_k] + c) :\n",
    "                        #     x[s] = tmp\n",
    "            dp = x\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # dp = [inf for _ in range(1 << n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(1 << n)]\n",
    "        #     for i, c in enumerate(row) :\n",
    "        #         for j, d in enumerate(dp) :\n",
    "        #             k = j | (1 << i)\n",
    "        #             x[k] = min(x[k], d + c, dp[k] + c, x[j] + c)\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "        m = len(cost)\n",
    "        n = len(cost[0])\n",
    "        n = 1 << n\n",
    "\n",
    "        dp = [inf for _ in range(n)]\n",
    "        dp[0] = 0\n",
    "        for row in cost :\n",
    "            x = [inf for _ in range(n)]\n",
    "            for s in range(n) :\n",
    "                for k, c in enumerate(row) :\n",
    "                    if s & (1 << k) :\n",
    "                        s_k = s ^ (1 << k)\n",
    "                        # x[s] = min(x[s], x[s_k] + c, dp[s] + c, dp[s_k] + c)\n",
    "                        if x[s] > (tmp := x[s_k] + c) :\n",
    "                            x[s] = tmp\n",
    "                        if x[s] > (tmp := dp[s] + c) :\n",
    "                            x[s] = tmp\n",
    "                        if x[s] > (tmp := dp[s_k] + c) :\n",
    "                            x[s] = tmp\n",
    "            dp = x\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # dp = [inf for _ in range(1 << n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(1 << n)]\n",
    "        #     for i, c in enumerate(row) :\n",
    "        #         for j, d in enumerate(dp) :\n",
    "        #             k = j | (1 << i)\n",
    "        #             x[k] = min(x[k], d + c, dp[k] + c, x[j] + c)\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "        m = len(cost)\n",
    "        n = len(cost[0])\n",
    "        n = 1 << n\n",
    "\n",
    "        dp = [inf for _ in range(n)]\n",
    "        dp[0] = 0\n",
    "        for row in cost :\n",
    "            x = [inf for _ in range(n)]\n",
    "            for s in range(n) :\n",
    "                for k, c in enumerate(row) :\n",
    "                    if s & (1 << k) :\n",
    "                        s_k = s ^ (1 << k)\n",
    "                        x[s] = min(x[s], x[s_k] + c, dp[s] + c, dp[s_k] + c)\n",
    "                        # if x[s] > (tmp := x[s_k] + c) :\n",
    "                        #     x[s] = tmp\n",
    "                        # if x[s] > (tmp := dp[s] + c) :\n",
    "                        #     x[s] = tmp\n",
    "                        # if x[s] > (tmp := dp[s_k] + c) :\n",
    "                        #     x[s] = tmp\n",
    "            dp = x\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 转化为带权二分图的最大匹配问题，使用基于Hungarian的KM算法求解\n",
    "\n",
    "class KM:\n",
    "    def __init__(self, m: int, n: int):\n",
    "        self.n = max(m, n)\n",
    "        self.lx = [0] * self.n  # 顶标\n",
    "        self.ly = [0] * self.n  # 顶标\n",
    "        self.cx = [-1] * self.n  # 匹配顶点下标\n",
    "        self.cy = [-1] * self.n  # 匹配顶点下标\n",
    "        self.cost = [[0] * self.n for _ in range(self.n)]  # 边权\n",
    "        self.ts = 0  # 时间戳\n",
    "        self.visx = [0] * self.n  # 顶点访问时间戳\n",
    "        self.visy = [0] * self.n  # 顶点访问时间戳\n",
    "        self.min_sub = 10 ** 9  # 添加新边的最小降低标准\n",
    "\n",
    "    def add_edge(self, u: int, v: int, w: int):\n",
    "        self.cost[u][v] = w\n",
    "\n",
    "    def dfs(self, i: int) -> bool:\n",
    "        self.visx[i] = self.ts\n",
    "        for j in range(self.n):\n",
    "            # 如果顶点j还没被试探过，且当前边(i,j)在相等子图中\n",
    "            if self.visy[j] < self.ts and self.lx[i] + self.ly[j] - self.cost[i][j] == 0:\n",
    "                self.visy[j] = self.ts\n",
    "                # 如果找到了增广路径，则将(i,j)加入匹配边\n",
    "                if self.cy[j] == -1 or self.dfs(self.cy[j]):\n",
    "                    self.cx[i] = j\n",
    "                    self.cy[j] = i\n",
    "                    return True\n",
    "            # 如果(i,j)不在相等子图中，则更新相等子图中加入新的边的最小降低标准\n",
    "            elif self.lx[i] + self.ly[j] - self.cost[i][j] > 0:\n",
    "                self.min_sub = min(\n",
    "                    self.min_sub, self.lx[i] + self.ly[j] - self.cost[i][j])\n",
    "        return False\n",
    "\n",
    "    def solve(self) -> int:\n",
    "        # 初始化顶标\n",
    "        self.lx = [max(self.cost[i][j] for j in range(self.n))\n",
    "                   for i in range(self.n)]\n",
    "        # print(self.lx)\n",
    "\n",
    "        # 枚举顶点进行匹配\n",
    "        for x in range(self.n):\n",
    "            while True:\n",
    "                self.ts += 1\n",
    "                self.min_sub = 10**9\n",
    "                if self.dfs(x):  # 匹配成功\n",
    "                    break\n",
    "                # 否则更新顶标\n",
    "                for i in range(self.n):\n",
    "                    if self.visx[i] == self.ts:\n",
    "                        self.lx[i] -= self.min_sub\n",
    "                for j in range(self.n):\n",
    "                    if self.visy[j] == self.ts:\n",
    "                        self.ly[j] += self.min_sub\n",
    "\n",
    "        # 计算匹配的边权总和\n",
    "        res = sum(self.cost[i][self.cx[i]] for i in range(self.n))\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "\n",
    "        # 转化为带权二分图的最大匹配问题\n",
    "\n",
    "        m, n = len(cost), len(cost[0])\n",
    "\n",
    "        # 先计算每个顶点的最小连边代价\n",
    "        min_cost_x = [10**9] * m\n",
    "        min_cost_y = [10**9] * n\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                min_cost_x[i] = min(min_cost_x[i], cost[i][j])\n",
    "                min_cost_y[j] = min(min_cost_y[j], cost[i][j])\n",
    "\n",
    "        # 计算所有最小代价的和为基本解\n",
    "        ans = sum(min_cost_x) + sum(min_cost_y)\n",
    "\n",
    "        # 重新定义边的权重，并计算新图的最大匹配权重和，用基本解减去最大匹配权重和即为答案\n",
    "        km = KM(m, n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                w = min_cost_x[i] + min_cost_y[j] - cost[i][j]\n",
    "                if w > 0:\n",
    "                    km.add_edge(i, j, w)\n",
    "        ans -= km.solve()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        f = [0] * (1 << len(cost[0]))\n",
    "        for j, mn in enumerate(map(min, zip(*cost))):\n",
    "            bit = 1 << j\n",
    "            for mask in range(bit):\n",
    "                f[bit | mask] = f[mask] + mn\n",
    "        for row in cost:\n",
    "            for j in range(len(f) - 1, -1, -1):\n",
    "                f[j] = min(f[j & ~(1 << k)] + c for k, c in enumerate(row))\n",
    "        return f[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        ##矩阵每行每列都至少选一个坐标\n",
    "        n,m=len(cost),len(cost[0])\n",
    "        f=[[0]*(1<<m) for _ in range(n+1)]\n",
    "        for i,col in enumerate(zip(*cost)):\n",
    "            f[0][1<<i]=min(col)\n",
    "        for j in range(1<<m):\n",
    "            f[0][j]=f[0][j&(j-1)]+f[0][j&(-j)]\n",
    "        for i, row in enumerate(cost):\n",
    "            for j in range(1 << m):\n",
    "                f[i + 1][j] = min(f[i][j & ~(1 << k)] + c\n",
    "                    for k, c in enumerate(row))\n",
    "        return f[n][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        size1 = len(cost)\n",
    "        size2 = len(cost[0])\n",
    "        m = 1 << size2\n",
    "        # dp = [[float('inf')] * m for _ in range(size1 + 1)]\n",
    "        # dp[0][0] = 0\n",
    "\n",
    "        # for i in range(1, size1 + 1):\n",
    "        #     for s in range(m):\n",
    "        #         for k in range(size2):\n",
    "        #             if (s & (1 << k)) == 0:\n",
    "        #                 continue\n",
    "        #             dp[i][s] = min(dp[i][s], dp[i][s ^ (1 << k)] + cost[i - 1][k])\n",
    "        #             dp[i][s] = min(dp[i][s], dp[i - 1][s] + cost[i - 1][k])\n",
    "        #             dp[i][s] = min(dp[i][s], dp[i - 1][s ^ (1 << k)] + cost[i - 1][k])\n",
    "        \n",
    "        # return dp[size1][m - 1]\n",
    "\n",
    "        dp1, dp2 = [float(\"inf\")] * m, [float(\"inf\")] * m\n",
    "        dp1[0] = 0\n",
    "\n",
    "        for i in range(1, size1 + 1):\n",
    "            for s in range(m):\n",
    "                dp2[s] = float(\"inf\")\n",
    "                for k in range(size2):\n",
    "                    if (s & (1 << k)) == 0:\n",
    "                        continue\n",
    "                    dp2[s] = min(dp2[s], dp2[s ^ (1 << k)] + cost[i - 1][k])\n",
    "                    dp2[s] = min(dp2[s], dp1[s] + cost[i - 1][k])\n",
    "                    dp2[s] = min(dp2[s], dp1[s ^ (1 << k)] + cost[i - 1][k])\n",
    "            dp1 = dp2[:]\n",
    "        \n",
    "        return dp1[m - 1]\n",
    "                        \n",
    "        \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # dp = [inf for _ in range(1 << n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(1 << n)]\n",
    "        #     for i, c in enumerate(row) :\n",
    "        #         for j, d in enumerate(dp) :\n",
    "        #             k = j | (1 << i)\n",
    "        #             x[k] = min(x[k], d + c, dp[k] + c, x[j] + c)\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "        m = len(cost)\n",
    "        n = len(cost[0])\n",
    "        n = 1 << n\n",
    "\n",
    "        dp = [inf for _ in range(n)]\n",
    "        dp[0] = 0\n",
    "        for row in cost :\n",
    "            x = [inf for _ in range(n)]\n",
    "            for s in range(n) :\n",
    "                for k, c in enumerate(row) :\n",
    "                    if s & (1 << k) :\n",
    "                        s_k = s ^ (1 << k)\n",
    "                        if x[s] > (tmp :=x[s_k] + c) :\n",
    "                            x[s] = tmp\n",
    "                        if x[s] > (tmp :=dp[s] + c) :\n",
    "                            x[s] = tmp\n",
    "                        if x[s] > (tmp :=dp[s_k] + c) :\n",
    "                            x[s] = tmp\n",
    "            dp = x\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # dp = [inf for _ in range(1 << n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(1 << n)]\n",
    "        #     for i, c in enumerate(row) :\n",
    "        #         for j, d in enumerate(dp) :\n",
    "        #             k = j | (1 << i)\n",
    "        #             x[k] = min(x[k], d + c, dp[k] + c, x[j] + c)\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "        m = len(cost)\n",
    "        n = len(cost[0])\n",
    "        n = 1 << n\n",
    "\n",
    "        dp = [inf for _ in range(n)]\n",
    "        dp[0] = 0\n",
    "        for row in cost :\n",
    "            x = [inf for _ in range(n)]\n",
    "            for s in range(n) :\n",
    "                for k, c in enumerate(row) :\n",
    "                    if s & (1 << k) :\n",
    "                        s_k = s ^ (1 << k)\n",
    "                        if x[s] > (tmp :=x[s_k] + c) :\n",
    "                            x[s] = tmp\n",
    "                        if x[s] > (tmp :=dp[s] + c) :\n",
    "                            x[s] = tmp\n",
    "                        if x[s] > (tmp :=dp[s_k] + c) :\n",
    "                            x[s] = tmp\n",
    "            dp = x\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # dp = [inf for _ in range(1 << n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(1 << n)]\n",
    "        #     for i, c in enumerate(row) :\n",
    "        #         for j, d in enumerate(dp) :\n",
    "        #             k = j | (1 << i)\n",
    "        #             x[k] = min(x[k], d + c, dp[k] + c, x[j] + c)\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # n = 1 << n\n",
    "\n",
    "        # dp = [inf for _ in range(n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(n)]\n",
    "        #     for s in range(n) :\n",
    "        #         for k, c in enumerate(row) :\n",
    "        #             if s & (1 << k) :\n",
    "        #                 s_k = s ^ (1 << k)\n",
    "        #                 # x[s] = min(x[s], x[s_k] + c, dp[s] + c, dp[s_k] + c)\n",
    "        #                 if x[s] > (tmp := x[s_k] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #                 if x[s] > (tmp := dp[s] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #                 if x[s] > (tmp := dp[s_k] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # min_cost = list(map(min, zip(*cost)))\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j) :\n",
    "        #     if i < 0 :\n",
    "        #         return sum(c for k, c in enumerate(min_cost) if j & (1 << k))\n",
    "        #     return min(dfs(i - 1, j & ~(1 << k)) + c for k, c in enumerate(cost[i]))\n",
    "        # return dfs(m - 1, (1 << n) - 1)\n",
    "\n",
    "\n",
    "        m = len(cost)\n",
    "        n = len(cost[0])\n",
    "        min_cost = list(map(min, zip(*cost)))\n",
    "        dp = [[0 for _ in range(1 << n)] for _ in range(m + 1)]\n",
    "\n",
    "        for j in range(1 << n) :\n",
    "            dp[0][j] = sum(c for k, c in enumerate(min_cost) if j & (1 << k))\n",
    "\n",
    "        for i, row in enumerate(cost) :\n",
    "            for j in range(1 << n) :\n",
    "                dp[i + 1][j] = min(dp[i][j & ~(1 << k)] + c for k, c in enumerate(row))\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # dp = [inf for _ in range(1 << n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(1 << n)]\n",
    "        #     for i, c in enumerate(row) :\n",
    "        #         for j, d in enumerate(dp) :\n",
    "        #             k = j | (1 << i)\n",
    "        #             x[k] = min(x[k], d + c, dp[k] + c, x[j] + c)\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "        m = len(cost)\n",
    "        n = len(cost[0])\n",
    "        n = 1 << n\n",
    "\n",
    "        dp = [inf for _ in range(n)]\n",
    "        dp[0] = 0\n",
    "        for row in cost :\n",
    "            x = [inf for _ in range(n)]\n",
    "            for s in range(n) :\n",
    "                for k, c in enumerate(row) :\n",
    "                    if s & (1 << k) :\n",
    "                        s_k = s ^ (1 << k)\n",
    "                        if x[s] > (tmp :=x[s_k] + c) :\n",
    "                            x[s] = tmp\n",
    "                        if x[s] > (tmp :=dp[s] + c) :\n",
    "                            x[s] = tmp\n",
    "                        if x[s] > (tmp :=dp[s_k] + c) :\n",
    "                            x[s] = tmp\n",
    "            dp = x\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: [[int]]) -> int:\n",
    "\n",
    "        nn=len(cost)            #第一组的人数\n",
    "        mm=len(cost[0])         #第二组的人数\n",
    "\n",
    "        dp = [[sys.maxsize] * (1 << mm) for i in range(nn)]\n",
    "\n",
    "        # dp[p][state] 第p个人选择后形成了 state状态的最小值\n",
    "        for p in range(nn):\n",
    "            #当前要处理第i个人\n",
    "            if p==0:\n",
    "                for k in range(mm):\n",
    "                    dp[p][1<<k]=cost[p][k]\n",
    "                continue\n",
    "\n",
    "            for prestate in range(1<<mm):\n",
    "                for k in range(mm):\n",
    "                    tmp=prestate|(1<<k)\n",
    "                    dp[p][tmp]=min(dp[p][tmp],dp[p-1][prestate]+cost[p][k])\n",
    "\n",
    "        hp=[sys.maxsize for i in range(mm)]\n",
    "        for i in range(nn):\n",
    "            for j in range(mm):\n",
    "                hp[j]=min(hp[j],cost[i][j])\n",
    "\n",
    "        ans=sys.maxsize\n",
    "        for state in range(1 << mm):\n",
    "            if dp[p][state]<sys.maxsize:\n",
    "                curcost=dp[p][state]\n",
    "                for k in range(mm):\n",
    "                    if state&(1<<k)==0:\n",
    "                        curcost+=hp[k]\n",
    "                ans=min(ans,curcost)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        m = len(cost)\n",
    "        n = len(cost[0])\n",
    "        dp = [inf for _ in range(1 << n)]\n",
    "        dp[0] = 0\n",
    "        for row in cost :\n",
    "            x = [inf for _ in range(1 << n)]\n",
    "            for i, c in enumerate(row) :\n",
    "                for j, d in enumerate(dp) :\n",
    "                    k = j | (1 << i)\n",
    "                    x[k] = min(x[k], d + c, dp[k] + c, x[j] + c)\n",
    "            dp = x\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class MinCostFlow:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.edges = [[] for i in range(n)]\n",
    "\n",
    "    def add_edge(self, fr, to, cap, cost):\n",
    "        self.edges[fr].append([to, cap, cost, len(self.edges[to])])\n",
    "        self.edges[to].append([fr, 0, -cost, len(self.edges[fr]) - 1])\n",
    "\n",
    "    def MinCost(self, source, sink, flow):\n",
    "        n = self.n;\n",
    "        E = self.edges\n",
    "        mincost = 0\n",
    "        prev_v = [0] * n;\n",
    "        prev_e = [0] * n\n",
    "        while flow:\n",
    "            dist = [inf] * n\n",
    "            dist[source] = 0\n",
    "            q = deque([source])\n",
    "            Flag = [False] * n\n",
    "            Flag[source] = True\n",
    "            while q:\n",
    "                v = q.popleft()\n",
    "                if not Flag[v]:\n",
    "                    continue\n",
    "                Flag[v] = False\n",
    "                for i, (to, cap, cost, _) in enumerate(E[v]):\n",
    "                    if cap > 0 and dist[to] > dist[v] + cost:\n",
    "                        dist[to] = dist[v] + cost\n",
    "                        prev_v[to], prev_e[to] = v, i\n",
    "                        q.append(to)\n",
    "                        Flag[to] = True\n",
    "            f, v = flow, sink\n",
    "            while v != source:\n",
    "                f = min(f, E[prev_v[v]][prev_e[v]][1])\n",
    "                v = prev_v[v]\n",
    "            flow -= f\n",
    "            mincost += f * dist[sink]\n",
    "            v = sink\n",
    "            while v != source:\n",
    "                E[prev_v[v]][prev_e[v]][1] -= f\n",
    "                rev = E[prev_v[v]][prev_e[v]][3]\n",
    "                E[v][rev][1] += f\n",
    "                v = prev_v[v]\n",
    "        return mincost\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, c: List[List[int]]) -> int:\n",
    "        m = len(c)\n",
    "        n = len(c[0])\n",
    "        col = [10**18] * m\n",
    "        row = [10**18] * n\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                col[i] = min(col[i],c[i][j])\n",
    "                row[j] = min(row[j],c[i][j])\n",
    "        dinic = MinCostFlow(n + m + 2)\n",
    "        start,end = 0,n + m + 1\n",
    "        for i in range(m):\n",
    "            dinic.add_edge(start,i + 1,1,0)\n",
    "        for i in range(n):\n",
    "            dinic.add_edge(i + 1 + m,end,1,0)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dinic.add_edge(i + 1,j + 1 + m,1,min(0,c[i][j] - row[j] - col[i]))\n",
    "        return sum(col) + sum(row) + dinic.MinCost(start,end,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        size1, size2 = len(cost), len(cost[0])\n",
    "        m = 1 << size2\n",
    "        dp1, dp2 = [float(\"inf\")] * m, [0] * m\n",
    "        dp1[0] = 0\n",
    "\n",
    "        for i in range(1, size1 + 1):\n",
    "            for s in range(m):\n",
    "                dp2[s] = float(\"inf\")\n",
    "                for k in range(size2):\n",
    "                    if (s & (1 << k)) == 0:\n",
    "                        continue\n",
    "                    dp2[s] = min(dp2[s], dp2[s ^ (1 << k)] + cost[i - 1][k])\n",
    "                    dp2[s] = min(dp2[s], dp1[s] + cost[i - 1][k])\n",
    "                    dp2[s] = min(dp2[s], dp1[s ^ (1 << k)] + cost[i - 1][k])\n",
    "            dp1 = dp2[:]\n",
    "        \n",
    "        return dp1[m - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # 获取第一组点和第二组点的大小\n",
    "        size1 = len(cost)\n",
    "        size2 = len(cost[0])\n",
    "\n",
    "        # 创建动态规划表，并初始化为正无穷\n",
    "        dp = [[float('inf')] * (1 << size2) for _ in range(size1 + 1)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        # 计算动态规划表\n",
    "        for i in range(size1):\n",
    "            for mask in range(1 << size2):\n",
    "                for j in range(size2):\n",
    "                    # 尝试连接第一组的点i和第二组的点j\n",
    "                    # 更新连接后的状态和成本\n",
    "                    dp[i + 1][mask | (1 << j)] = min(dp[i + 1][mask | (1 << j)], dp[i][mask] + cost[i][j])\n",
    "                    dp[i + 1][mask] = min(dp[i + 1][mask], dp[i][mask] + cost[i][j])\n",
    "\n",
    "        # 找到最小成本\n",
    "        min_cost = float('inf')\n",
    "        for mask in range(1 << size2):\n",
    "            total_cost = dp[size1][mask]\n",
    "            for j in range(size2):\n",
    "                if not mask & (1 << j):\n",
    "                    # 对于未连接的第二组的点，找到连接它们的最小成本\n",
    "                    total_cost += min(cost[i][j] for i in range(size1))\n",
    "            min_cost = min(min_cost, total_cost)\n",
    "\n",
    "        # 返回最小成本\n",
    "        return min_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        size1 = len(cost)\n",
    "        size2 = len(cost[0])\n",
    "        m = 1 << size2\n",
    "        # dp = [[float('inf')] * m for _ in range(size1 + 1)]\n",
    "        # dp[0][0] = 0\n",
    "\n",
    "        # for i in range(1, size1 + 1):\n",
    "        #     for s in range(m):\n",
    "        #         for k in range(size2):\n",
    "        #             if (s & (1 << k)) == 0:\n",
    "        #                 continue\n",
    "        #             dp[i][s] = min(dp[i][s], dp[i][s ^ (1 << k)] + cost[i - 1][k])\n",
    "        #             dp[i][s] = min(dp[i][s], dp[i - 1][s] + cost[i - 1][k])\n",
    "        #             dp[i][s] = min(dp[i][s], dp[i - 1][s ^ (1 << k)] + cost[i - 1][k])\n",
    "        \n",
    "        # return dp[size1][m - 1]\n",
    "\n",
    "        dp1, dp2 = [float(\"inf\")] * m, [float(\"inf\")] * m\n",
    "        dp1[0] = 0\n",
    "\n",
    "        for i in range(1, size1 + 1):\n",
    "            for s in range(m):\n",
    "                dp2[s] = float(\"inf\")\n",
    "                for k in range(size2):\n",
    "                    if (s & (1 << k)) == 0:\n",
    "                        continue\n",
    "                    dp2[s] = min(dp2[s], dp2[s ^ (1 << k)] + cost[i - 1][k])\n",
    "                    dp2[s] = min(dp2[s], dp1[s] + cost[i - 1][k])\n",
    "                    dp2[s] = min(dp2[s], dp1[s ^ (1 << k)] + cost[i - 1][k])\n",
    "            dp1 = dp2[:]\n",
    "        \n",
    "        return dp1[m - 1]\n",
    "                        \n",
    "        \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        N, M = len(cost), len(cost[0])\n",
    "        size = 2** M\n",
    "        DP = [[float('inf')] * size for _ in range(N+1)]\n",
    "        DP[0][0] = 0\n",
    "\n",
    "        for i in range(1,N+1):\n",
    "            for k in range(size):\n",
    "                for s in range(M):\n",
    "                    if (k & (1<< s))==0:\n",
    "                        continue\n",
    "                    DP[i][k] = min(DP[i][k], DP[i][k & ~(1<<s)] + cost[i - 1][s])\n",
    "                    DP[i][k] = min(DP[i][k], DP[i-1][k] + cost[i-1][s]) # i只连s\n",
    "                    DP[i][k] = min(DP[i][k], DP[i-1][k & ~(1 << s)] + cost[i - 1][s])\n",
    "\n",
    "        return DP[N][size - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        size1,size2=len(cost),len(cost[0])\n",
    "        m = 1 << size2\n",
    "        dp = [[float(\"inf\")] * m for _ in range(size1 + 1)]\n",
    "        dp[0][0]=0\n",
    "\n",
    "        for i in range(1,size1+1):\n",
    "            for s in range(m):\n",
    "                for k in range(size2):\n",
    "                    if (s & (1 << k)) == 0:\n",
    "                        continue\n",
    "                    dp[i][s] = min(dp[i][s], dp[i][s ^ (1 << k)] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s ^ (1 << k)] + cost[i - 1][k])\n",
    "        return dp[size1][m-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # dp = [inf for _ in range(1 << n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(1 << n)]\n",
    "        #     for i, c in enumerate(row) :\n",
    "        #         for j, d in enumerate(dp) :\n",
    "        #             k = j | (1 << i)\n",
    "        #             x[k] = min(x[k], d + c, dp[k] + c, x[j] + c)\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # n = 1 << n\n",
    "\n",
    "        # dp = [inf for _ in range(n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(n)]\n",
    "        #     for s in range(n) :\n",
    "        #         for k, c in enumerate(row) :\n",
    "        #             if s & (1 << k) :\n",
    "        #                 s_k = s ^ (1 << k)\n",
    "        #                 # x[s] = min(x[s], x[s_k] + c, dp[s] + c, dp[s_k] + c)\n",
    "        #                 if x[s] > (tmp := x[s_k] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #                 if x[s] > (tmp := dp[s] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #                 if x[s] > (tmp := dp[s_k] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # min_cost = list(map(min, zip(*cost)))\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j) :\n",
    "        #     if i < 0 :\n",
    "        #         return sum(c for k, c in enumerate(min_cost) if j & (1 << k))\n",
    "        #     return min(dfs(i - 1, j & ~(1 << k)) + c for k, c in enumerate(cost[i]))\n",
    "        # return dfs(m - 1, (1 << n) - 1)\n",
    "\n",
    "\n",
    "        m = len(cost)\n",
    "        n = len(cost[0])\n",
    "        min_cost = list(map(min, zip(*cost)))\n",
    "        dp = [[0 for _ in range(1 << n)] for _ in range(m + 1)]\n",
    "\n",
    "        for j in range(1 << n) :\n",
    "            dp[0][j] = sum(c for k, c in enumerate(min_cost) if j & (1 << k))\n",
    "\n",
    "        for i, row in enumerate(cost) :\n",
    "            for j in range(1 << n) :\n",
    "                dp[i + 1][j] = min(dp[i][j & ~(1 << k)] + c for k, c in enumerate(row))\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        m,n=len(cost),len(cost[0])\n",
    "        dp=[[inf]*(1<<n) for _ in range(m+1)]\n",
    "        dp[0][0]=0\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1<<n):\n",
    "                for k in range(n):\n",
    "                    if (j>>k&1)==0: continue\n",
    "                    a=min(dp[i][j^(1<<k)],dp[i-1][j],dp[i-1][j^(1<<k)])+cost[i-1][k]\n",
    "                    dp[i][j]=min(dp[i][j],a)\n",
    "        return dp[m][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        size1 = len(cost)\n",
    "        size2 = len(cost[0])\n",
    "        m = 1 << size2\n",
    "        dp = [[float('inf')] * m for _ in range(size1 + 1)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i in range(1, size1 + 1):\n",
    "            for s in range(m):\n",
    "                for k in range(size2):\n",
    "                    if (s & (1 << k)) == 0:\n",
    "                        continue\n",
    "                    dp[i][s] = min(dp[i][s], dp[i][s ^ (1 << k)] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s ^ (1 << k)] + cost[i - 1][k])\n",
    "        \n",
    "        return dp[size1][m - 1]\n",
    "\n",
    "        # dp1, dp2 = [float(\"inf\")] * m, [float(\"inf\")] * m\n",
    "        # dp1[0] = 0\n",
    "\n",
    "        # for i in range(1, size1 + 1):\n",
    "        #     for s in range(m):\n",
    "        #         dp2[s] = float(\"inf\")\n",
    "        #         for k in range(size2):\n",
    "        #             if (s & (1 << k)) == 0:\n",
    "        #                 continue\n",
    "        #             dp2[s] = min(dp2[s], dp2[s ^ (1 << k)] + cost[i - 1][k])\n",
    "        #             dp2[s] = min(dp2[s], dp1[s] + cost[i - 1][k])\n",
    "        #             dp2[s] = min(dp2[s], dp1[s ^ (1 << k)] + cost[i - 1][k])\n",
    "        #     dp1 = dp2[:]\n",
    "        \n",
    "        # return dp1[m - 1]\n",
    "                        \n",
    "        \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        size1,size2 = len(cost),len(cost[0])\n",
    "        m = 1<<size2\n",
    "        dp = [[float(\"inf\")] * m for _ in range(size1+1)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i in range(1,size1+1):\n",
    "            for s in range(m):\n",
    "                for k in range(size2):\n",
    "                    if(s & (1<<k)) == 0:\n",
    "                        continue\n",
    "                    dp[i][s] = min(dp[i][s],dp[i][s^(1<<k)] + cost[i-1][k]) \n",
    "                    dp[i][s] = min(dp[i][s],dp[i-1][s] + cost[i-1][k]) \n",
    "                    dp[i][s] = min(dp[i][s],dp[i-1][s^(1<<k)] + cost[i-1][k]) \n",
    "        \n",
    "        return dp[size1][m-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        size1, size2 = len(cost), len(cost[0])\n",
    "        m = 1 << size2\n",
    "        dp = [[float(\"inf\")] * m for _ in range(size1 + 1)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i in range(1, size1 + 1):\n",
    "            for s in range(m):\n",
    "                for k in range(size2):\n",
    "                    if (s & (1 << k)) == 0:\n",
    "                        continue\n",
    "                    dp[i][s] = min(dp[i][s], dp[i][s ^ (1 << k)] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s ^ (1 << k)] + cost[i - 1][k])\n",
    "        \n",
    "        return dp[size1][m - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # dp = [inf for _ in range(1 << n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(1 << n)]\n",
    "        #     for i, c in enumerate(row) :\n",
    "        #         for j, d in enumerate(dp) :\n",
    "        #             k = j | (1 << i)\n",
    "        #             x[k] = min(x[k], d + c, dp[k] + c, x[j] + c)\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # n = 1 << n\n",
    "\n",
    "        # dp = [inf for _ in range(n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(n)]\n",
    "        #     for s in range(n) :\n",
    "        #         for k, c in enumerate(row) :\n",
    "        #             if s & (1 << k) :\n",
    "        #                 s_k = s ^ (1 << k)\n",
    "        #                 # x[s] = min(x[s], x[s_k] + c, dp[s] + c, dp[s_k] + c)\n",
    "        #                 if x[s] > (tmp := x[s_k] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #                 if x[s] > (tmp := dp[s] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #                 if x[s] > (tmp := dp[s_k] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # min_cost = list(map(min, zip(*cost)))\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j) :\n",
    "        #     if i < 0 :\n",
    "        #         return sum(c for k, c in enumerate(min_cost) if j & (1 << k))\n",
    "        #     return min(dfs(i - 1, j & ~(1 << k)) + c for k, c in enumerate(cost[i]))\n",
    "        # return dfs(m - 1, (1 << n) - 1)\n",
    "\n",
    "\n",
    "        m = len(cost)\n",
    "        n = len(cost[0])\n",
    "        min_cost = list(map(min, zip(*cost)))\n",
    "        dp = [[0 for _ in range(1 << n)] for _ in range(m + 1)]\n",
    "\n",
    "        for j in range(1 << n) :\n",
    "            dp[0][j] = sum(c for k, c in enumerate(min_cost) if j & (1 << k))\n",
    "\n",
    "        for i, row in enumerate(cost) :\n",
    "            for j in range(1 << n) :\n",
    "                dp[i + 1][j] = min(dp[i][j & ~(1 << k)] + c for k, c in enumerate(row))\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        size1,size2=len(cost),len(cost[0])\n",
    "        m = 1 << size2\n",
    "        dp = [[float(\"inf\")] * m for _ in range(size1 + 1)]\n",
    "        dp[0][0]=0\n",
    "\n",
    "        for i in range(1,size1+1):\n",
    "            for s in range(m):\n",
    "                for k in range(size2):\n",
    "                    if (s & (1 << k)) == 0:\n",
    "                        continue\n",
    "                    dp[i][s] = min(dp[i][s], dp[i][s ^ (1 << k)] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s ^ (1 << k)] + cost[i - 1][k])\n",
    "        return dp[size1][m-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        size1 = len(cost)\n",
    "        size2 = len(cost[0])\n",
    "        m = 1 << size2\n",
    "        dp = [[float('inf')] * m for _ in range(size1 + 1)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i in range(1, size1 + 1):\n",
    "            for s in range(m):\n",
    "                for k in range(size2):\n",
    "                    if (s & (1 << k)) == 0:\n",
    "                        continue\n",
    "                    dp[i][s] = min(dp[i][s], dp[i][s ^ (1 << k)] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s ^ (1 << k)] + cost[i - 1][k])\n",
    "        \n",
    "        return dp[size1][m - 1]\n",
    "                        \n",
    "        \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # 先标记二组的所有点，每次取最小的之后再剩下的点中选取最小的，再之后，当所有二\n",
    "        # 组点遍历完毕之后，我们后面只需要选取最小的点\n",
    "        # 这样设计会有一个问题 要是不是最小的点在前面，前面是比较大的选了后面是比较小的\n",
    "        # res = 0\n",
    "        # point2IsView = [0] * len(cost[0])\n",
    "        # for i in range(len(cost)):\n",
    "        #     if sum(point2IsView) == len(cost[0]):\n",
    "        #         res += min(cost[i])\n",
    "        #     else:\n",
    "        #         min_value = 999 \n",
    "        #         min_index_i,min_index_j = [],[]\n",
    "        #         for j in range(len(cost[i])):\n",
    "        #             if cost[i][j] <= min_value and point2IsView[j] == 0:\n",
    "        #                 min_value = cost[i][j]\n",
    "        #                 min_index_i.append(i)\n",
    "        #                 min_index_j.append(j)\n",
    "        #         for min_i,min_j in zip(min_index_i,min_index_j):\n",
    "        #             if cost[min_i][min_j] == min_value:\n",
    "        #                 point2IsView[min_j] = 1\n",
    "        #                 res += min_value\n",
    "        # return res\n",
    "                        \n",
    "\n",
    "        size1, size2 = len(cost), len(cost[0])\n",
    "        m = 1 << size2\n",
    "        dp = [[float(\"inf\")] * m for _ in range(size1 + 1)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i in range(1, size1 + 1):\n",
    "            for s in range(m):\n",
    "                for k in range(size2):\n",
    "                    if (s & (1 << k)) == 0:\n",
    "                        continue\n",
    "                    dp[i][s] = min(dp[i][s], dp[i][s ^ (1 << k)] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s ^ (1 << k)] + cost[i - 1][k])\n",
    "        \n",
    "        return dp[size1][m - 1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        size1, size2 = len(cost), len(cost[0])\n",
    "        m = 1 << size2\n",
    "        dp = [[float(\"inf\")] * m for _ in range(size1 + 1)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i in range(1, size1 + 1):\n",
    "            for s in range(m):\n",
    "                for k in range(size2):\n",
    "                    if (s & (1 << k)) == 0:\n",
    "                        continue\n",
    "                    dp[i][s] = min(dp[i][s], dp[i][s ^ (1 << k)] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s ^ (1 << k)] + cost[i - 1][k])\n",
    "        \n",
    "        return dp[size1][m - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        m=len(cost)\n",
    "        n=len(cost[0])\n",
    "        state=1<<n\n",
    "\n",
    "        dp=[[float(\"inf\")]*state for _ in range(m+1)]\n",
    "        dp[0][0]=0\n",
    "        for i in range(m+1):\n",
    "            for s in range(state):\n",
    "                for j in range(n):\n",
    "                    if s&(1<<j)==0:\n",
    "                        continue\n",
    "                    dp[i][s]=min(dp[i][s],dp[i][s^(1<<j)]+cost[i-1][j])\n",
    "                    dp[i][s]=min(dp[i][s],dp[i-1][s]+cost[i-1][j])\n",
    "                    dp[i][s]=min(dp[i][s],dp[i-1][s^(1<<j)]+cost[i-1][j])\n",
    "        #print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        size1 = len(cost)\n",
    "        size2 = len(cost[0])\n",
    "        m = 1 << size2\n",
    "        dp = [[float('inf')] * m for _ in range(size1 + 1)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i in range(1, size1 + 1):\n",
    "            for s in range(m):\n",
    "                for k in range(size2):\n",
    "                    if (s & (1 << k)) == 0:\n",
    "                        continue\n",
    "                    dp[i][s] = min(dp[i][s], dp[i][s - (1 << k)] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s - (1 << k)] + cost[i - 1][k])\n",
    "        \n",
    "        return dp[size1][m - 1]\n",
    "                        \n",
    "        \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        size1, size2 = len(cost), len(cost[0])\n",
    "        m = 1 << size2\n",
    "        dp = [[float(\"inf\")] * m for _ in range(size1 + 1)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i in range(1, size1 + 1):\n",
    "            for s in range(m):\n",
    "                for k in range(size2):\n",
    "                    if (s & (1 << k)) == 0:\n",
    "                        continue\n",
    "                    dp[i][s] = min(dp[i][s], dp[i][s ^ (1 << k)] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s ^ (1 << k)] + cost[i - 1][k])\n",
    "        \n",
    "        return dp[size1][m - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: list[list[int]]) -> int:\n",
    "        \n",
    "        size1, size2 = len(cost), len(cost[0])\n",
    "        m = 1 << size2\n",
    "        dp = [[float(\"inf\")] * m for _ in range(size1 + 1)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i in range(1, size1 + 1):\n",
    "            for s in range(m):\n",
    "                for k in range(size2):\n",
    "                    if (s & (1 << k)) == 0:\n",
    "                        continue\n",
    "                    dp[i][s] = min(dp[i][s], dp[i][s ^ (1 << k)] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s ^ (1 << k)] + cost[i - 1][k])\n",
    "        \n",
    "        return dp[size1][m - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        s1,s2 = len(cost), len(cost[0])\n",
    "        dp = [[float('inf')] * (1 << s2) for _ in range(s1 +1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, s1+1):\n",
    "            for j in range(1, 1 << s2):\n",
    "                for k in range(s2):\n",
    "                    if (j >> k) & 1:\n",
    "                        j_k = j & (~(1<<k))\n",
    "                        tmp = min(dp[i][j_k] + cost[i-1][k], dp[i-1][j] + cost[i-1][k], dp[i-1][j_k] + cost[i-1][k])\n",
    "                        dp[i][j] = min(dp[i][j], tmp)\n",
    "        \n",
    "        return dp[s1][(1<<s2)-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        size1 = len(cost)\n",
    "        size2 = len(cost[0])\n",
    "        m = 1 << size2\n",
    "        dp = [[float('inf')] * m for _ in range(size1 + 1)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i in range(1, size1 + 1):\n",
    "            for s in range(m):\n",
    "                for k in range(size2):\n",
    "                    if (s & (1 << k)) == 0:\n",
    "                        continue\n",
    "                    dp[i][s] = min(dp[i][s], dp[i][s ^ (1 << k)] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s] + cost[i - 1][k])\n",
    "                    dp[i][s] = min(dp[i][s], dp[i - 1][s ^ (1 << k)] + cost[i - 1][k])\n",
    "        \n",
    "        return dp[size1][m - 1]\n",
    "\n",
    "        # dp1, dp2 = [float(\"inf\")] * m, [float(\"inf\")] * m\n",
    "        # dp1[0] = 0\n",
    "\n",
    "        # for i in range(1, size1 + 1):\n",
    "        #     for s in range(m):\n",
    "        #         dp2[s] = float(\"inf\")\n",
    "        #         for k in range(size2):\n",
    "        #             if (s & (1 << k)) == 0:\n",
    "        #                 continue\n",
    "        #             dp2[s] = min(dp2[s], dp2[s ^ (1 << k)] + cost[i - 1][k])\n",
    "        #             dp2[s] = min(dp2[s], dp1[s] + cost[i - 1][k])\n",
    "        #             dp2[s] = min(dp2[s], dp1[s ^ (1 << k)] + cost[i - 1][k])\n",
    "        #     dp1 = dp2[:]\n",
    "        \n",
    "        # return dp1[m - 1]\n",
    "                        \n",
    "        \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        row = len(cost)\n",
    "        col = len(cost[0])\n",
    "        #组1 任选组2 连一次\n",
    "        dcost={}\n",
    "        dp=[(1<<col)-1]\n",
    "        dcost[(1<<col)-1]=0\n",
    "        ans=-1\n",
    "        for r in range(row):\n",
    "            ndp=[]\n",
    "            ncost={}\n",
    "            for gcol in dp:\n",
    "                spent=dcost[gcol]       \n",
    "                for j in range(col):\n",
    "                    cspent=spent+cost[r][j]\n",
    "                    ncol=gcol\n",
    "                    if (1<<j)|gcol==gcol:\n",
    "                        ncol=gcol^(1<<j)\n",
    "                    if ncol not in ncost:\n",
    "                        ncost[ncol]=cspent\n",
    "                        ndp.append(ncol)\n",
    "                    else:\n",
    "                        if cspent<ncost[ncol]:\n",
    "                            ncost[ncol]=cspent\n",
    "            dp=ndp\n",
    "            dcost=ncost\n",
    "        ans=-1\n",
    "        for left in dp:\n",
    "            spent=dcost[left]\n",
    "            for c in range(col):\n",
    "                if (1<<c)|left==left:\n",
    "                    spent+=min([cost[x][c] for x in range(row)])\n",
    "            if ans==-1:\n",
    "                ans=spent\n",
    "            else:\n",
    "                ans=min(spent,ans)\n",
    "\n",
    "        return ans\n",
    "                        \n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        m=len(cost)\n",
    "        n=len(cost[0])\n",
    "        state=1<<n\n",
    "\n",
    "        dp=[[float(\"inf\")]*state for _ in range(m+1)]\n",
    "        dp[0][0]=0\n",
    "        for i in range(m+1):\n",
    "            for s in range(state):\n",
    "                for j in range(n):\n",
    "                    if s&(1<<j)==0:\n",
    "                        continue\n",
    "                    dp[i][s]=min(dp[i][s],dp[i][s^(1<<j)]+cost[i-1][j])\n",
    "                    dp[i][s]=min(dp[i][s],dp[i-1][s]+cost[i-1][j])\n",
    "                    dp[i][s]=min(dp[i][s],dp[i-1][s^(1<<j)]+cost[i-1][j])\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        dp[i][mask] 连接 i 和 mask 表示的集合的人连通的最少花费\n",
    "        \"\"\"\n",
    "        M, N = len(cost), len(cost[0])\n",
    "        dp = [[float(\"inf\") for j in range(1 << N)] for i in range(M + 1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(M):\n",
    "            for mask in range(1 << N):\n",
    "                for j in range(N):\n",
    "                    dp[i + 1][mask | (1 << j)] = min(\n",
    "                        dp[i + 1][mask | (1 << j)], \n",
    "                        dp[i][mask] + cost[i][j]\n",
    "                    )\n",
    "                    dp[i + 1][mask | (1 << j)] = min(\n",
    "                        dp[i + 1][mask | (1 << j)], \n",
    "                        dp[i + 1][mask] + cost[i][j]\n",
    "                    )\n",
    "        return dp[M][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 状压DP，dp[i][j]表示前i个左侧数已经根j所表示的二进制位的右侧的数匹配时，后续完成两组点连通的最小代价\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "\n",
    "        m,  n = len(cost), len(cost[0])\n",
    "        dp = [[-1] * (1 << n) for _ in range(m + 1)]\n",
    "\n",
    "        mask = (1 << n) - 1\n",
    "        minCostY = [10 ** 9] * n\n",
    "        # print(minCostY)\n",
    "        for row in cost:\n",
    "            for j, c in enumerate(row):\n",
    "                minCostY[j] = min(minCostY[j], c)\n",
    "\n",
    "        def dfs(i: int, choose: int) -> int:\n",
    "            # nonlocal dp\n",
    "            if dp[i][choose] >= 0:\n",
    "                return dp[i][choose]\n",
    "            if i == m:\n",
    "                oriChoose = choose\n",
    "                choose = (choose ^ mask) & mask\n",
    "                res = 0\n",
    "                while choose:\n",
    "                    # print(choose & (-choose))\n",
    "                    lst = (choose & (-choose)).bit_length() - 1\n",
    "                    # print(lst)\n",
    "                    res += minCostY[lst]\n",
    "                    choose &= (choose - 1)\n",
    "                dp[i][oriChoose] = res\n",
    "                return res\n",
    "            res = 10 ** 9\n",
    "            for j in range(n):\n",
    "                res = min(res,  cost[i][j] + dfs(i + 1, choose | (1 << j)))\n",
    "            dp[i][choose] = res\n",
    "            return res\n",
    "        ans = dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        size1,size2=len(cost),len(cost[0])\n",
    "        m=1<<size2\n",
    "        dp=[[float(\"inf\") for _ in range(m)] for _ in range(size1+1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1,size1+1):\n",
    "            for s in range(m):\n",
    "                for k in range(size2):\n",
    "                    if (s&(1<<k))==0:\n",
    "                        continue\n",
    "                    dp[i][s]=min(dp[i][s],dp[i][s^(1<<k)]+cost[i-1][k])\n",
    "                    dp[i][s]=min(dp[i][s],dp[i-1][s]+cost[i-1][k])\n",
    "                    dp[i][s]=min(dp[i][s],dp[i-1][s^(1<<k)]+cost[i-1][k])\n",
    "        return dp[size1][m-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        q = []\n",
    "        m = len(cost)\n",
    "        n = len(cost[0])\n",
    "\n",
    "        @cache\n",
    "        def dp(idx, s):\n",
    "            if idx == 0 and s == 0:\n",
    "                return 0\n",
    "            elif idx == 0:\n",
    "                return inf\n",
    "            elif s == 0:\n",
    "                return inf\n",
    "\n",
    "            ret = inf\n",
    "\n",
    "            for j, c in enumerate(cost[idx - 1]):\n",
    "                if s & (1 << j) == 0:\n",
    "                    continue\n",
    "\n",
    "                t = s ^ (1 << j)\n",
    "\n",
    "                ret = min(ret, dp(idx - 1, s) + c)\n",
    "                ret = min(ret, dp(idx, t) + c)\n",
    "                ret = min(ret, dp(idx - 1, t) + c)\n",
    "\n",
    "            return ret\n",
    "\n",
    "        ret = dp(m, (1 << n) - 1)\n",
    "        dp.cache_clear()\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        n, m = len(cost), len(cost[0])\n",
    "        min_cost = [min(col) for col in zip(*cost)]  # 每一列的最小值\n",
    "\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0:\n",
    "                return sum(c for k, c in enumerate(min_cost) if j >> k & 1)\n",
    "            return min(dfs(i - 1, j & ~(1 << k)) + c\n",
    "                       for k, c in enumerate(cost[i]))  # 第一组的点 i 与第二组的点 k\n",
    "        return dfs(n - 1, (1 << m) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        n, m = len(cost), len(cost[0])\n",
    "        min_cost = [min(col) for col in zip(*cost)]\n",
    "\n",
    "        @cache\n",
    "\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0:\n",
    "                return sum(c for k, c in enumerate(min_cost) if (j >> k) & 1)\n",
    "            return min(dfs(i - 1, j &~ (1 << k)) + c \n",
    "            for k, c in enumerate(cost[i]))\n",
    "        return dfs(n - 1, (1 << m) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        ##矩阵每行每列都至少选一个坐标\n",
    "        n,m=len(cost),len(cost[0])\n",
    "        minCost=[min(col) for col in zip(*cost)]\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,nodes):\n",
    "            if i<0:\n",
    "                return sum(c for k,c in enumerate(minCost) if nodes&(1<<k))\n",
    "            return min(dfs(i-1,nodes&~(1<<k))+c for k,c in enumerate(cost[i]))\n",
    "        return dfs(n-1,(1<<m)-1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        m, n = len(cost), len(cost[0])\n",
    "        min_cost = [min(col) for col in zip(*cost)]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i < 0:\n",
    "                return sum(c for k, c in enumerate(min_cost) if not j >> k & 1)\n",
    "            return min(dfs(i - 1, j | 1 << k) + c for k, c in enumerate(cost[i]))\n",
    "        return dfs(m - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        n, m = len(cost), len(cost[0])\n",
    "        min_cost = [min(col) for col in zip(*cost)]  # 每一列的最小值\n",
    "\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0:\n",
    "                return sum(c for k, c in enumerate(min_cost) if j >> k & 1)\n",
    "            return min(dfs(i - 1, j & ~(1 << k)) + c\n",
    "                       for k, c in enumerate(cost[i]))  # 第一组的点 i 与第二组的点 k\n",
    "        return dfs(n - 1, (1 << m) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        n, m = len(cost), len(cost[0])\n",
    "        min_cost = [min(col) for col in zip(*cost)] \n",
    "\n",
    "        @cache \n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0:\n",
    "                return sum(c for k, c in enumerate(min_cost) if j >> k & 1)\n",
    "            return min(dfs(i - 1, j & ~(1 << k)) + c\n",
    "                       for k, c in enumerate(cost[i]))  \n",
    "        return dfs(n - 1, (1 << m) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # cost 表示邻接表中的权重，返回最小连接权重和，两组必须连通，且size1 >= size2\n",
    "\n",
    "        # n, m = len(cost), len(cost[0])\n",
    "        # min_cost = [min(col) for col in zip(*cost)] # 每一列的最小值\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i: int, j:int) -> int: # dfs(i,j)表示第一组的[0...i]和第二组的[0...m-]且第二组的集合j未被连接时的最小成本\n",
    "        #     if i < 0:\n",
    "        #         return sum(c for k, c in enumerate(min_cost) if j >> k & 1)\n",
    "        #     return min(dfs(i - 1, j & ~(1 << k)) + c for k, c in enumerate(cost[i]))\n",
    "        # return dfs(n - 1, (1 << m) - 1) \n",
    "\n",
    "        n, m = len(cost), len(cost[0])\n",
    "        min_cost = [min(col) for col in zip(*cost)] \n",
    "\n",
    "        @cache\n",
    "        def dfs(i:int, j:int) -> int: \n",
    "            if i < 0:\n",
    "                return sum(c for k, c in enumerate(min_cost) if j >> k & 1)\n",
    "            return min(dfs(i - 1, j & ~(1 << k)) + c for k, c in enumerate(cost[i]))\n",
    "        return dfs(n - 1, (1 << m) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        n, m = len(cost), len(cost[0])\n",
    "        min_cost = [min(col) for col in zip(*cost)]  # 每一列的最小值\n",
    "\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0:\n",
    "                return sum(c for k, c in enumerate(min_cost) if j >> k & 1)\n",
    "            return min(dfs(i - 1, j & ~(1 << k)) + c\n",
    "                       for k, c in enumerate(cost[i]))  # 第一组的点 i 与第二组的点 k\n",
    "        return dfs(n - 1, (1 << m) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        n, m = len(cost), len(cost[0])\n",
    "        min_cost = [min(col) for col in zip(*cost)]  # 每一列的最小值\n",
    "\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0:\n",
    "                return sum(c for k, c in enumerate(min_cost) if j >> k & 1)\n",
    "            return min(dfs(i - 1, j & ~(1 << k)) + c\n",
    "                       for k, c in enumerate(cost[i]))  # 第一组的点 i 与第二组的点 k\n",
    "        return dfs(n - 1, (1 << m) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        n, m = len(cost), len(cost[0])\n",
    "        min_cost = [min(col) for col in zip(*cost)]  # 每一列的最小值\n",
    "\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0:\n",
    "                return sum(c for k, c in enumerate(min_cost) if j >> k & 1)\n",
    "            return min(dfs(i - 1, j & ~(1 << k)) + c\n",
    "                       for k, c in enumerate(cost[i]))  # 第一组的点 i 与第二组的点 k\n",
    "        return dfs(n - 1, (1 << m) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        m, n = len(cost), len(cost[0])\n",
    "\n",
    "        low = [min(cost[i][j] for i in range(m)) for j in range(n)]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, state):\n",
    "            if i == m:\n",
    "                res = 0\n",
    "                for j in range(n):\n",
    "                    if not state & (1<<j):\n",
    "                        res += low[j]\n",
    "                return res\n",
    "            return min(dfs(i+1, state|(1<<j))+cost[i][j] for j in range(n))\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 1595. 连通两组点的最小成本\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # dfs[i][j]：前i个第一组的点，覆盖第二组的点状态为j时的最小成本\n",
    "        # 状态转移：ret = min(ret,dfs(i-1,pre|cur)+cost[cur])\n",
    "        # 边界情况：如果j==full return 0 else return inf\n",
    "        n, m = len(cost), len(cost[0])\n",
    "        full = 1 << m\n",
    "\n",
    "        # 预处理出第二组和第一组中连接的最低代价\n",
    "        paid = [inf] * m\n",
    "        for j in range(m):\n",
    "            for i in range(n):\n",
    "                paid[j] = min(paid[j],cost[i][j])              \n",
    "\n",
    "        @cache\n",
    "        def dfs(i, state):\n",
    "            if i == 0:\n",
    "                sum = 0\n",
    "                for bit in range(m):\n",
    "                    if not (state&(1<<bit)):\n",
    "                        sum += paid[bit]\n",
    "                return sum    \n",
    "\n",
    "            ret = inf\n",
    "            for j in range(0, m):\n",
    "                ret = min(ret, dfs(i - 1, state | (1<<j) ) + cost[i-1][j]  )\n",
    "\n",
    "            return ret\n",
    "\n",
    "        return dfs(n, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        m=len(cost)#第一组点的数量\n",
    "        n=len(cost[0])#第二组点的数量\n",
    "        #min_cost[i]: 第二组中的点连接第一组的最小代价\n",
    "        min_cost=[]\n",
    "        for j in range(n):\n",
    "            min_val=float('inf')\n",
    "            for i in range(m):\n",
    "                min_val=min(min_val, cost[i][j])\n",
    "            min_cost.append(min_val)\n",
    "        @cache\n",
    "        def dfs(i, mask):\n",
    "            if i<0:\n",
    "                temp=0\n",
    "                for k,c in enumerate(min_cost):\n",
    "                    if (mask>>k)&1:\n",
    "                        temp+=c\n",
    "                return temp\n",
    "            res=float('inf')\n",
    "            for k,c in enumerate(cost[i]):\n",
    "                # 第k个数没取\n",
    "                #if mask&(1<<k):\n",
    "                res=min(dfs(i-1, mask&(~(1<<k)))+c,res)\n",
    "            return res\n",
    "\n",
    "        return dfs(m-1, (1<<n)-1)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        n, m = len(cost), len(cost[0])\n",
    "        min_cost = [min(col) for col in zip(*cost)]  # 每一列的最小值\n",
    "\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0:\n",
    "                return sum(c for k, c in enumerate(min_cost) if j >> k & 1)\n",
    "            return min(dfs(i - 1, j & ~(1 << k)) + c\n",
    "                       for k, c in enumerate(cost[i]))  # 第一组的点 i 与第二组的点 k\n",
    "        return dfs(n - 1, (1 << m) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # cost 表示邻接表中的权重，返回最小连接权重和\n",
    "\n",
    "        n, m = len(cost), len(cost[0])\n",
    "        min_cost = [min(col) for col in zip(*cost)] # 每一列的最小值\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j:int) -> int: # dfs(i,j)表示第一组的[0...i]和第二组的[0...m-]且第二组的集合j未被连接时的最小成本\n",
    "            if i < 0:\n",
    "                return sum(c for k, c in enumerate(min_cost) if j >> k & 1)\n",
    "            return min(dfs(i - 1, j & ~(1 << k)) + c for k, c in enumerate(cost[i]))\n",
    "        return dfs(n - 1, (1 << m) - 1) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        n, m = len(cost), len(cost[0])\n",
    "        min_cost = [min(col) for col in zip(*cost)]  # 每一列的最小值\n",
    "\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0:\n",
    "                return sum(c for k, c in enumerate(min_cost) if j >> k & 1)\n",
    "            return min(dfs(i - 1, j & ~(1 << k)) + c\n",
    "                       for k, c in enumerate(cost[i]))  # 第一组的点 i 与第二组的点 k\n",
    "        return dfs(n - 1, (1 << m) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # dp = [inf for _ in range(1 << n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(1 << n)]\n",
    "        #     for i, c in enumerate(row) :\n",
    "        #         for j, d in enumerate(dp) :\n",
    "        #             k = j | (1 << i)\n",
    "        #             x[k] = min(x[k], d + c, dp[k] + c, x[j] + c)\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # n = 1 << n\n",
    "\n",
    "        # dp = [inf for _ in range(n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(n)]\n",
    "        #     for s in range(n) :\n",
    "        #         for k, c in enumerate(row) :\n",
    "        #             if s & (1 << k) :\n",
    "        #                 s_k = s ^ (1 << k)\n",
    "        #                 # x[s] = min(x[s], x[s_k] + c, dp[s] + c, dp[s_k] + c)\n",
    "        #                 if x[s] > (tmp := x[s_k] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #                 if x[s] > (tmp := dp[s] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #                 if x[s] > (tmp := dp[s_k] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "        m = len(cost)\n",
    "        n = len(cost[0])\n",
    "        min_cost = list(map(min, zip(*cost)))\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j) :\n",
    "            if i < 0 :\n",
    "                return sum(c for k, c in enumerate(min_cost) if j & (1 << k))\n",
    "            return min(dfs(i - 1, j & ~(1 << k)) + c for k, c in enumerate(cost[i]))\n",
    "        return dfs(m - 1, (1 << n) - 1)\n",
    "\n",
    "\n",
    "        # n, m = len(cost), len(cost[0])\n",
    "        # min_cost = [min(col) for col in zip(*cost)]  # 每一列的最小值\n",
    "\n",
    "        # @cache  # 记忆化搜索\n",
    "        # def dfs(i: int, j: int) -> int:\n",
    "        #     if i < 0:\n",
    "        #         return sum(c for k, c in enumerate(min_cost) if j >> k & 1)\n",
    "        #     return min(dfs(i - 1, j & ~(1 << k)) + c\n",
    "        #                for k, c in enumerate(cost[i]))  # 第一组的点 i 与第二组的点 k\n",
    "        # return dfs(n - 1, (1 << m) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # dp = [inf for _ in range(1 << n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(1 << n)]\n",
    "        #     for i, c in enumerate(row) :\n",
    "        #         for j, d in enumerate(dp) :\n",
    "        #             k = j | (1 << i)\n",
    "        #             x[k] = min(x[k], d + c, dp[k] + c, x[j] + c)\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # n = 1 << n\n",
    "\n",
    "        # dp = [inf for _ in range(n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(n)]\n",
    "        #     for s in range(n) :\n",
    "        #         for k, c in enumerate(row) :\n",
    "        #             if s & (1 << k) :\n",
    "        #                 s_k = s ^ (1 << k)\n",
    "        #                 # x[s] = min(x[s], x[s_k] + c, dp[s] + c, dp[s_k] + c)\n",
    "        #                 if x[s] > (tmp := x[s_k] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #                 if x[s] > (tmp := dp[s] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #                 if x[s] > (tmp := dp[s_k] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "        m = len(cost)\n",
    "        n = len(cost[0])\n",
    "        min_cost = list(map(min, zip(*cost)))\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j) :\n",
    "            if i < 0 :\n",
    "                return sum(c for k, c in enumerate(min_cost) if j & (1 << k))\n",
    "            return min(dfs(i - 1, j & ~(1 << k)) + c for k, c in enumerate(cost[i]))\n",
    "        return dfs(m - 1, (1 << n) - 1)\n",
    "\n",
    "\n",
    "        # n, m = len(cost), len(cost[0])\n",
    "        # min_cost = [min(col) for col in zip(*cost)]  # 每一列的最小值\n",
    "\n",
    "        # @cache  # 记忆化搜索\n",
    "        # def dfs(i: int, j: int) -> int:\n",
    "        #     if i < 0:\n",
    "        #         return sum(c for k, c in enumerate(min_cost) if j >> k & 1)\n",
    "        #     return min(dfs(i - 1, j & ~(1 << k)) + c\n",
    "        #                for k, c in enumerate(cost[i]))  # 第一组的点 i 与第二组的点 k\n",
    "        # return dfs(n - 1, (1 << m) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # cost 表示邻接表中的权重，返回最小连接权重和\n",
    "\n",
    "        n, m = len(cost), len(cost[0])\n",
    "        min_cost = [min(col) for col in zip(*cost)] # 每一列的最小值\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j:int) -> int:\n",
    "            if i < 0:\n",
    "                return sum(c for k, c in enumerate(min_cost) if j >> k & 1)\n",
    "            return min(dfs(i - 1, j & ~(1 << k)) + c for k, c in enumerate(cost[i]))\n",
    "        return dfs(n - 1, (1 << m) - 1) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        n, m = len(cost), len(cost[0])\n",
    "        min_cost = [min(col) for col in zip(*cost)]  # 每一列的最小值\n",
    "\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0:\n",
    "                return sum(c for k, c in enumerate(min_cost) if j >> k & 1)\n",
    "            return min(dfs(i - 1, j & ~(1 << k)) + c\n",
    "                       for k, c in enumerate(cost[i]))  # 第一组的点 i 与第二组的点 k\n",
    "        return dfs(n - 1, (1 << m) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        n, m = len(cost), len(cost[0])\n",
    "        min_cost = [min(col) for col in zip(*cost)]  # 每一列的最小值\n",
    "\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0:\n",
    "                return sum(c for k, c in enumerate(min_cost) if j >> k & 1)\n",
    "            return min(dfs(i - 1, j & ~(1 << k)) + c\n",
    "                       for k, c in enumerate(cost[i]))  # 第一组的点 i 与第二组的点 k\n",
    "        return dfs(n - 1, (1 << m) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # dp = [inf for _ in range(1 << n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(1 << n)]\n",
    "        #     for i, c in enumerate(row) :\n",
    "        #         for j, d in enumerate(dp) :\n",
    "        #             k = j | (1 << i)\n",
    "        #             x[k] = min(x[k], d + c, dp[k] + c, x[j] + c)\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "        # m = len(cost)\n",
    "        # n = len(cost[0])\n",
    "        # n = 1 << n\n",
    "\n",
    "        # dp = [inf for _ in range(n)]\n",
    "        # dp[0] = 0\n",
    "        # for row in cost :\n",
    "        #     x = [inf for _ in range(n)]\n",
    "        #     for s in range(n) :\n",
    "        #         for k, c in enumerate(row) :\n",
    "        #             if s & (1 << k) :\n",
    "        #                 s_k = s ^ (1 << k)\n",
    "        #                 # x[s] = min(x[s], x[s_k] + c, dp[s] + c, dp[s_k] + c)\n",
    "        #                 if x[s] > (tmp := x[s_k] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #                 if x[s] > (tmp := dp[s] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #                 if x[s] > (tmp := dp[s_k] + c) :\n",
    "        #                     x[s] = tmp\n",
    "        #     dp = x\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "        m = len(cost)\n",
    "        n = len(cost[0])\n",
    "        min_cost = list(map(min, zip(*cost)))\n",
    "        # min_cost = map(min, zip(*cost))\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j) :\n",
    "            if i < 0 :\n",
    "                # return sum(c for k, c in enumerate(min_cost) if j & (1 << k))\n",
    "                print(j, tmp := sum(c for k, c in enumerate(min_cost) if j & (1 << k)))\n",
    "                return tmp\n",
    "            return min(dfs(i - 1, j & ~(1 << k)) + c for k, c in enumerate(cost[i]))\n",
    "        return dfs(m - 1, (1 << n) - 1)\n",
    "\n",
    "\n",
    "        # n, m = len(cost), len(cost[0])\n",
    "        # min_cost = [min(col) for col in zip(*cost)]  # 每一列的最小值\n",
    "\n",
    "        # @cache  # 记忆化搜索\n",
    "        # def dfs(i: int, j: int) -> int:\n",
    "        #     if i < 0:\n",
    "        #         return sum(c for k, c in enumerate(min_cost) if j >> k & 1)\n",
    "        #     return min(dfs(i - 1, j & ~(1 << k)) + c\n",
    "        #                for k, c in enumerate(cost[i]))  # 第一组的点 i 与第二组的点 k\n",
    "        # return dfs(n - 1, (1 << m) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        i = len(cost)\n",
    "        j = len(cost[0])\n",
    "\n",
    "        minCost = [min(i) for i in zip(*cost)]\n",
    "\n",
    "        @cache \n",
    "        def dp(i, rest):\n",
    "            if i < 0: return sum(c for k, c in enumerate(minCost) if rest >> k & 1)\n",
    "            \n",
    "            res = inf\n",
    "            for n in range(j):\n",
    "                res = min(res, dp(i - 1, rest & ~(1 << n)) + cost[i][n])\n",
    "            return res\n",
    "        \n",
    "        return dp(i - 1, (1 << j) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        m=len(cost)\n",
    "        n=len(cost[0])\n",
    "        dp=defaultdict(int)\n",
    "        def dfs(idx):\n",
    "            if dp[idx]==0:\n",
    "                # s1=idx>>4\n",
    "                s2=idx&15\n",
    "                res=inf\n",
    "                if s2<n:\n",
    "                    for i in range(m):\n",
    "                        res=min(res,dfs((idx|1<<(i+4))+1)+cost[i][s2])\n",
    "                else:\n",
    "                    res=0\n",
    "                    for i,x in enumerate(cost):\n",
    "                        if (idx>>(i+4))&1==0:\n",
    "                            print(x)\n",
    "                            res+=min(x)\n",
    "                dp[idx]=res\n",
    "                # print(idx)\n",
    "                # print(dp)\n",
    "            return dp[idx]\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        m, n = len(cost), len(cost[0])\n",
    "        # 预处理，记录每一行的最小值\n",
    "        row_min = [min(x) for x in cost]\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, mask: int) -> int:\n",
    "            if i == n:\n",
    "                # 填充没有选到的行，未选到的行贪心选最小值即可\n",
    "                return sum(row_min[j] for j in range(m) if (mask >> j) & 1 == 0)\n",
    "\n",
    "            res = inf\n",
    "            # 枚举第i列选哪一行\n",
    "            for j in range(m):\n",
    "                res = min(res, dfs(i + 1, mask | (1 << j)) + cost[j][i])\n",
    "            return res\n",
    "        return dfs(0, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
